Euler Problem 193

A positive integer n is called squarefree, if no square of a prime divides n, thus 1, 2, 3, 5, 6, 7, 10, 11 are squarefree, but not 4, 8, 9, 12.

How many squarefree numbers are there below 2⁵⁰?



In [1]:

    
from sympy import sieve
N = 2**25
NN = N*N - 1
mobius = [0, 1, -1, 1] * ((N+3) // 4)
mobius[0] = 1
for p in sieve.primerange(3, N):
    for n in range(p, N, p):
        mobius[n] = -mobius[n]
    pp = p*p
    for n in range(pp, N, pp):
        mobius[n] = 0
print(sum(int(NN/(d*d)) * mobius[d] 
          for d in range(1, N)))









    



684465067343069



In [ ]: